package leecode;

import org.junit.Test;

import java.util.*;

public class No0003_LongestSubstringWithoutRepeatingCharacters {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int start = -1;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c) && map.get(c) > start) {
                start = map.get(c);
            }
            map.put(c, i);
            max = Math.max(max, i - start);
        }
        return max;
    }


    public int lengthOfLongestSubstring2(String s) {
        Set<Character> set = new HashSet<>();
        Queue<Character> queue = new LinkedList<>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                while (!Objects.equals(c, queue.peek())) {
                    set.remove(queue.poll());
                }
                set.remove(queue.poll());
            }
            set.add(c);
            queue.add(c);
            max = Math.max(max, set.size());

        }
        return max;
    }


    @Test
    public void test() {
        No0003_LongestSubstringWithoutRepeatingCharacters no3 = new No0003_LongestSubstringWithoutRepeatingCharacters();
        System.out.println(no3.lengthOfLongestSubstring("abba"));
    }

}
